package com.hfmcoding;

import java.util.*;
import java.io.*;

public class HFMNode implements Comparable<HFMNode>, Serializable {// 哈夫曼树中的一个节点
    private static final long serialVersionUID = 1L;
    public int weight;// 节点权值
    public char letter;// 节点代表的字符
    public int code;// 到这个节点的编码,前面补一个1位表示开始，以区分001与0001
    public HFMNode leftchild = null;// 节点的左孩子
    public HFMNode rightchild = null;// 节点的右孩子
    public HFMNode parent = null;// 节点的双亲

    public HFMNode(int weight, char letter, int code, HFMNode leftchild, HFMNode rightchild,
            HFMNode parent) {
        this.weight = weight;
        this.letter = letter;
        this.code = code;
        this.leftchild = leftchild;
        this.rightchild = rightchild;
        this.parent = parent;
        return;
    }

    @Override
    public int compareTo(HFMNode isBigOne) {
        // 通过权值比较哈夫曼节点
        if (this.weight < isBigOne.weight)
            return 1;
        else
            return -1;
    }

    public void getHFMCode(Map<Character, Integer> codeMap) {
        // 通过先序遍历哈夫曼树获得哈夫曼编码
        HFMNode currentNode = this;
        HFMNodeList nodeStack = new HFMNodeList();// 先序遍历用到的栈
        nodeStack.add(this);
        nodeStack.add(this);
        while (!nodeStack.isEmpty()) {// 先序遍历，从高往低计算出每个节点处的编码，叶子节点便存入字符的哈夫曼编码的Map中
            while (currentNode.leftchild != null && (currentNode.leftchild).code == 1) {
                currentNode = currentNode.leftchild;
                currentNode.code = (currentNode.parent).code * 2 + 0;
                nodeStack.add(currentNode);
            }
            if (currentNode.rightchild != null && (currentNode.rightchild).code == 1) {
                currentNode = currentNode.rightchild;
                currentNode.code = (currentNode.parent).code * 2 + 1;
                nodeStack.add(currentNode);
            } else {
                if (currentNode.rightchild == null && currentNode.leftchild == null) {
                    codeMap.put(currentNode.letter, currentNode.code);
                }
                currentNode = nodeStack.remove(nodeStack.size() - 1);
            }
        }
        return;
    }

    public String[] readHFMCode(String bitCode) {
        // 通过哈夫曼编码取得对应字符
        String[] answerString = new String[2];
        char thisletter;
        HFMNode current = this;
        while ((bitCode.length() > 0) && (current.leftchild != null || current.rightchild != null)) {
            if (bitCode.charAt(0) == '0')
                current = current.leftchild;
            if (bitCode.charAt(0) == '1')
                current = current.rightchild;
            bitCode = bitCode.replaceFirst("" + bitCode.charAt(0), "");
        }
        thisletter = current.letter;
        answerString[0] = thisletter + "";
        answerString[1] = bitCode;
        return answerString;
    }
}

class HFMNodeList extends ArrayList<HFMNode> {
    public void insertHFMNode(HFMNode NewHFMNode) {
        // 将节点按权值由小到大的顺序插入
        int listSize = this.size();
        if (this.size() == 0 || (this.get(0)).compareTo(NewHFMNode) == -1) {
            this.add(0, NewHFMNode);
            return;
        }
        for (int i = 0; i < listSize - 1; i++) {
            if ((this.get(i)).compareTo(NewHFMNode) == 1
                    && (this.get(i + 1)).compareTo(NewHFMNode) == -1) {
                this.add(i + 1, NewHFMNode);
                return;
            }
        }
        this.add(NewHFMNode);
        return;
    }

    public void getHFMNode(String inFilePath, String letterAndWeightPath) throws IOException {
        // 统计文件字符出现的次数并保留在Map中
        Character thisletter;
        Integer thisweight;
        int thisletterInt;
        Map<Character, Integer> weightMap = new HashMap<Character, Integer>();
        InputStreamReader input = new InputStreamReader(new FileInputStream(inFilePath), "UTF-8");
        while ((thisletterInt = input.read()) != -1) {
            thisletter = (char) thisletterInt;
            thisweight = weightMap.get(thisletter);
            if (thisweight == null)
                weightMap.put(thisletter, 1);
            else
                weightMap.put(thisletter, thisweight + 1);
        }
        input.close();
        // 根据字符的权值创建节点，并写入文件保存
        ObjectOutputStream output = new ObjectOutputStream(new FileOutputStream(letterAndWeightPath));
        Set<Character> keySet = weightMap.keySet();
        Iterator<Character> it = keySet.iterator();
        while (it.hasNext()) {
            Character key = it.next();
            Integer value = weightMap.get(key);
            HFMNode current = new HFMNode(value, key, 1, null, null, null);
            this.insertHFMNode(current);
        }
        int nodeListSize = this.size();
        for (int i = 0; i <= nodeListSize - 1; i++) {
            output.writeObject(this.get(i));
        }
        output.close();
        return;
    }

    public void readHFMNode(String letterAndWeightPath) throws ClassNotFoundException, IOException {
        // 读取创建的节点
        HFMNode current;
        ObjectInputStream input = new ObjectInputStream(new FileInputStream(letterAndWeightPath));
        while (true) {
            try {
                current = (HFMNode) input.readObject();
                this.add(current);
            } catch (EOFException e) {
                break;
            }
        }
        input.close();
        return;
    }

    public HFMNode getHFMTree() {
        // 通过节点数组构造哈夫曼树
        while (this.size() >= 2) {
            HFMNode parentNode = new HFMNode((this.get(0)).weight + (this.get(1)).weight, '\0', 1,
                    this.get(0), this.get(1), null);
            this.get(0).parent = this.get(1).parent = parentNode;
            this.insertHFMNode(parentNode);
            this.remove(0);
            this.remove(0);
        }
        HFMNode current=this.get(0);
        while(current.leftchild.leftchild!=null)
        current=current.leftchild;
        HFMNode newleft=new HFMNode(1, '\0', 1, null, null, null);
        HFMNode newnode=new HFMNode(current.leftchild.weight+1,'\0', 1, newleft, current.leftchild,current);
        newleft.parent=newnode;
        current.leftchild.parent=newnode;
        current.leftchild=newnode;
        return this.get(0);
    }
}